# -*- encoding: utf-8 -*-
"""
@author: CarpeDiem
@data: 22/9/22
@version: 0.1
@description: 
@method: 
思路一：统计坏数对，直接双重循环，时间复杂度为O(n^2)，超时
思路二：利用哈希表映射，算出数量相同的值元素与索引差值不一样的，利用排列组合的知识，可以知道这些不符合要求
"""

'''
def countBadPairs(nums):
    count = 0
    length = len(nums)
    for i in range(length):
        for j in range(i+1, length):
            if j - i != nums[j] - nums[i]:
                count += 1
    return count
'''

def countBadPairs(nums):
    count = 0
    temp_dict = dict()
    length = len(nums)
    for i in range(len(nums)):
        temp = nums[i] - i
        temp_dict[temp] = temp_dict.get(temp, 0) + 1
    for value in temp_dict.values():
        count += int(value * (value - 1) / 2)

    return int(length * (length - 1) / 2) - count


def main():
    print(countBadPairs([1, 2, 3, 4, 5]))
    print(countBadPairs([4, 1, 3, 3]))

main()